/**
 * Created by L.jp
 * Description:给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一个数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
 输入：l1 = [2,4,3], l2 = [5,6,4]
 输出：[7,0,8]
 解释：342 + 465 = 807.

 * User: 86189
 * Date: 2022-02-12
 * Time: 15:37
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    /*   第一步：拿到两个节点的值，空节点需要补0，方便构造新节点时的计算
         第二步：计算出两个节点的总和值sum，需要加上上一节点的进位值
         第三步：计算出当前位的进位值，tmp=sum/10;
         第四步：计算新链表的节点值，也就是真正留下来的和值，sum=sum%10;
         第五步：构造新链表节点，cur.next=new ListNode(sum)
         第六步：继续遍历l1,l2,按以上步骤构造新链表
         最后：当两个链表都遍历完了，需要判断进位值，如果进位值为1，那么就需要再构造一个新的节点，把进位值放进去
    *
    * */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //对于需要返回一个新的头结点的题目，我们通常需要构造一个虚拟头节点，以防找不到真正的头结点
        //由这个题目我们知道我们需要根据l1,l2构造出一个新的链表，并不是直接ListNode cur=new ListNode(0),cur=cur.next
        //这样不行，因为我们没有构造出一个链表，都是null值，所以走不下去，我们需要通过循环累加l1和l2的节点值来构造一个链表
        ListNode pre=new ListNode(0);//构造一个新链表的虚拟节点
        ListNode cur=pre;//遍用于遍历新的链表
        int tmp=0;//涉及到十进制加法，所以要存储进位，取值只有0和1的情况
        //开始构造新链表
        while(l1!=null || l2!=null){  //两个链表的长度不一样，只要其中一个链表遍历完了就可以退出循环
            //拿到当前两个链表节点的值
            int x=l1==null ? 0 : l1.val;//如果链表节点是空的，那么要补0，因为这个加法
            int y=l2==null ? 0 : l2.val;
            //拿到节点的和
            int sum=x+y+tmp;//节点的和包括l1,l2,以及进位值三个值之和，每计算一个节点的和值都要加上上一次的进位值
            //求得当前节点的进位值，以便下一节点使用
            tmp=sum/10;
            sum%=10;//这个才是真正的和值，不会超过10
            //开始构造链表
            cur.next=new ListNode(sum);
            cur=cur.next;
            //继续遍历l2,l2
            if(l1!=null){
                l1=l1.next;
            }
            if(l2 != null){
                l2=l2.next;
            }
        }
        //当两个链表遍历完了，那么我们构造新链表时需要知道上一次的进位值
        if(tmp==1){
            cur.next = new ListNode(1);//如果为1，那么就构造一个1，如果为0就不需要构造
        }
        return pre.next;
    }

}
